package com.likou.second_challenge;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class q438 {

    // 优化
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();

        int sN = s.length();
        int pN = p.length();
        if (sN < pN) {
            return new ArrayList<Integer>();
        }

        int[] pCount = new int[26];
        int[] sCount = new int[26];
        for (int i = 0; i < pN; i++) {
            pCount[p.charAt(i) - 'a']++;
            sCount[s.charAt(i) - 'a']++;
        }
        if (Arrays.equals(pCount, sCount)) {
            ans.add(0);
        }

        for (int i = 0; i < sN - pN; i++) {
            sCount[s.charAt(i) - 'a']--;
            sCount[s.charAt(pN + i) - 'a']++;

            if (Arrays.equals(pCount, sCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }

//    public List<Integer> findAnagrams(String s, String p) {
//        List<Integer> ans = new ArrayList<>();
//
//        int sN = s.length();
//        int pN = p.length();
//
//        int[] pCount = new int[26];
//        for (int i = 0; i < pN; i++) {
//            pCount[p.charAt(i) - 'a']++;
//        }
//
//        int left = 0;
//        int right = pN - 1;
//
//        for (; right < sN; right++, left++) {
//            int[] sCount = new int[26];
//            for (int i = left; i <= right; i++) {
//                sCount[s.charAt(i) - 'a']++;
//            }
//            if (Arrays.equals(pCount, sCount)) {
//                ans.add(left);
//            }
//        }
//
//        return ans;
//    }

}
